package com.jwetherell.my.problems.backtracking;

import java.util.Calendar;

/**
 * It prints one of the possible solutions(knight tour) in 2D matrix form. Basically, the
 * output is a 2D 8*8 matrix with numbers from 0 to 63 and these numbers show
 * steps made by Knight.
 * 
 * @author yatendra
 * 
 */
public class KnightTour {

	private int[][] chessBoard = new int[8][8];
	private int currentMoveRepresenter = 1;
	private int totalMoves = 8 * 8;
	private int [] xx = new int[] {-1, +1, -1, +1, -2, -2, +2, -2};
	private int [] yy = new int[] {-2, -2, +2, +2, +1, -1, +1, -1};

	
	public static void main(String[] args) {
		KnightTour knightTour = new KnightTour();
		knightTour.clearChessBoard();
		knightTour.printChessBoard();

		knightTour.makeMove(0,0);

		Calendar cal = Calendar.getInstance();
		long startTime = cal.getTimeInMillis();
		System.out.println("Start time: " + cal.get(Calendar.HOUR) + ":" + cal.get(Calendar.MINUTE) + ":" + cal.get(Calendar.SECOND));
		String resultStr = knightTour.printKnightTour(0,0) ? "Tour found" : "Tour not found";
		System.out.println(resultStr);
		long totalTimeTaken = (System.currentTimeMillis() - startTime)/(1000 * 60);
		System.out.println("Time taken: " + totalTimeTaken + " min.");
	}

	private boolean printKnightTour(int x, int y) {
		if (isAllSquaresVisited(currentMoveRepresenter)) {
			printChessBoard();
			return true;
		}

		int moveX;
		int moveY;
		for (int i = 0; i < 8; i++) {
			moveX = x+xx[i];
			moveY = y+yy[i];
			if (isValidMove(moveX, moveY)) {
				makeMove(moveX, moveY);
				
				if (printKnightTour(moveX, moveY))
					return true;
				
				revertMove(moveX, moveY); // backtracking
			}
		}
		
		return false;
	}

	private void makeMove(int x, int y) {
		chessBoard[x][y] = ++currentMoveRepresenter;
	}

	private void revertMove(int x, int y) {
		chessBoard[x][y] = -1;
		--currentMoveRepresenter;
	}

	// valid
	private boolean isValidMove(int x, int y) {

		if (x>=0 && x<=7 && y>=0 && y<=7 && chessBoard[x][y] == -1)
			return true;

		return false;
	}
	
	private void clearChessBoard() {
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard[0].length; j++) {
				chessBoard[i][j] = -1;
			}
		}
	}

	private void printChessBoard() {
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard[0].length; j++) {
				if (chessBoard[i][j] >= 0 && chessBoard[i][j] <= 9)
					System.out.print(" ");
				System.out.print(chessBoard[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private boolean isAllSquaresVisited(int currentMove) {
		return currentMove == totalMoves ? true : false;
	}
}